package solution.design;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * @author zhangmin
 * @create 2021-10-28 15:20
 * 设计题：380. O(1) 时间插入、删除和获取随机元素
 */
public class RandomizedSet {

    //数组用来存储元素
    ArrayList<Integer> nums;
    //map用来存储每个元素对应的索引
    HashMap<Integer,Integer> valToTindex;
    Random rand = new Random();
    public RandomizedSet() {
        nums=new ArrayList<>();
        valToTindex=new HashMap<>();
    }

    //当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
    public boolean insert(int val) {
        if (valToTindex.containsKey(val)){
            return false;
        }
        valToTindex.put(val,nums.size());
        nums.add(val);
        return true;
    }

    // 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
    public boolean remove(int val) {
        if (!valToTindex.containsKey(val))
            return false;
        //先拿到val的索引
        Integer i = valToTindex.get(val);
        //将最后一个元素放到i位置
        int lastInd=nums.size()-1;
        int lastNum=nums.get(lastInd);
        nums.set(i,lastNum);
        //删除nums中的最后一个元素
        nums.remove(lastInd);
        //将map中的映射改了
        valToTindex.put(lastNum,i);
        valToTindex.remove(val);
        return true;
    }

    //随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }

}
